#ifndef MSC_VECTOR_H
#define MSC_VECTOR_H

#include "mem_base.h"
#include <string.h>

#define MS_VECTOR_STEP  16

// c vector

typedef struct ms_vector_s{
    ms_alloc_t* ac; //内存管理工具
    size_t step;    //最小增量
    size_t size;    //元素尺寸
    size_t count;   //当前元素个数
    size_t max_count;   //当前元素最大存储个数
    unsigned char* first;    //当前元素首地址
    ms_class_t fs;
} ms_vector_t, *ms_vector;

CPUBLIC ms_vector ms_vector_create(ms_alloc_t* ac, size_t step, size_t size, ms_class_t* fs) {
    if (size) {
        if (!ac) {
            ac = ms_global_alloc();
        }
		ms_vector v = (ms_vector)ms_allocate(ac, sizeof(ms_vector_t));
        if (v) {
            v->ac = ac;
            if (step)
                v->step = step;
            else
                v->step = MS_VECTOR_STEP;
            v->size = size;
            v->count = 0;
            v->max_count = 0;
            v->first = NULL;
            ms_type_initclass(&v->fs, fs);
        }
        return v;
    }
    return NULL;
}

CPUBLIC void ms_vector_clear(ms_vector v) {
    if (v) {
        for (size_t i=0;i<v->count;++i) {
            v->fs.destroy(v->first+i*v->size);
        }
        v->count = 0;
        if (v->max_count > v->step) {
           ms_deallocate(v->ac, v->first);
           v->max_count = v->count = 0;
           v->first = NULL;
        }
        else {
            memset(v->first, 0, v->count*v->size);
            v->count = 0;
        }
    }
}

CPUBLIC void ms_vector_destory(ms_vector v) {
#ifdef _IF_NULL_
    if (v) {
#endif
    if (v->first) {
        for (size_t i=0;i<v->count;++i) {
            v->fs.destroy(v->first+i*v->size);
        }
        ms_deallocate(v->ac,v->first);
    }
    ms_deallocate(v->ac, v);
#ifdef _IF_NULL_
    }
#endif
}
CPUBLIC bool ms_vector_empty(ms_vector v) {
    return (NULL == v) || (0 == v->count);
}

CPUBLIC size_t ms_vector_size(ms_vector v) {
#ifdef _IF_NULL_
    if (v) {
#endif
    return v->count;
#ifdef _IF_NULL_
    }
    return 0;
#endif
}

CPUBLIC size_t ms_vector_capacity(ms_vector v) {
#ifdef _IF_NULL_
    if (v) {
#endif
    return v->max_count;
#ifdef _IF_NULL_
    }
    return 0;
#endif
}

CPUBLIC size_t ms_vector_max_size(ms_vector v) {
#ifdef _IF_NULL_
    if (v && v->size) {
#endif
    return ((size_t)-1)/v->size;
#ifdef _IF_NULL_
    }
    return 0;
#endif
}

static inline void ms_vector_reallocate(ms_vector v, size_t count) {
	if (v->first) {
		void* newp = NULL;
		if (v->ac->reallocate) {
            newp = ms_reallocate(v->ac, v->first, count*v->size);
		}
		else {
            newp = ms_allocate(v->ac, count*v->size);
			if (newp) {
				memcpy(newp, v->first, v->count*v->size);
                ms_deallocate(v->ac, v->first);
				v->first = NULL;
			}
		}
		if (newp) {
			v->max_count = count;
			v->first = (unsigned char*)newp;
		}
	}
	else {
        v->first = (unsigned char*)ms_allocate(v->ac, count*v->size);
		if (v->first) {
			v->max_count = count;
		}
	}
}

CPUBLIC size_t ms_vector_reserve(ms_vector v, size_t count) {
#ifdef _IF_NULL_
    if (v) {
#endif
    if (v->max_count < count  && count < ms_vector_max_size(v)) {
        ms_vector_reallocate(v,count);
    }
    return v->max_count;
#ifdef _IF_NULL_
    }
    return 0;
#endif
}

CPUBLIC size_t ms_vector_resize(ms_vector v, size_t count) {
#ifdef _IF_NULL_
    if (v) {
#endif
    if (count != v->max_count && count < ms_vector_max_size(v)) {
        if (count < v->count) {
            if (v->fs.destroy != ms_type_used) {
                for (size_t i=count;i<v->count;++i) {
                    void* data = v->first+v->size*i;
                    v->fs.destroy(data);
                }
            }
            v->count = count;
        }
        ms_vector_reallocate(v,count);
        if (count > v->count) {
            if (v->fs.construct != ms_type_used) {
                for (size_t i=v->count;i<count;++i) {
                    void* data = v->first+v->size*i;
                    v->fs.construct(data);
                }
            }
            v->count = count;
        }
    }
    return v->max_count;
#ifdef _IF_NULL_
    }
    return 0;
#endif
}

static inline void ms_vector_grow(ms_vector v) {
    size_t new_count = (v->max_count+v->step)/v->step*v->step;
    if (new_count < ms_vector_max_size(v))
        ms_vector_reallocate(v, new_count);
}
CPUBLIC void* ms_vector_push_back(ms_vector v, void* data) {
#ifdef _IF_NULL_
    if (v) {
#endif
    if (v->count == v->max_count) {
        ms_vector_grow(v);
    }
    if (v->count < v->max_count) {
        //赋值
        void* thisp = v->first+v->size*v->count;
        v->fs.construct(thisp);
        v->fs.copy(thisp, data);
        ++v->count;
        return thisp;
    }
#ifdef _IF_NULL_
    }
#endif
    return NULL;
}

CPUBLIC void ms_vector_pop_back(ms_vector v) {
    if (!ms_vector_empty(v)) {
        void* last = v->first+v->size*(v->count-1);
        v->fs.destroy(last);
        --v->count;
        if (v->count < v->max_count / 2 && v->count > v->step) {
            size_t new_count = (v->count+v->step)/v->step*v->step;
            ms_vector_reallocate(v, new_count);
        }
    }
}

CPUBLIC void* ms_vector_front(ms_vector v) {
#ifdef _IF_NULL_
    if (!ms_vector_empty(v)) {
#endif
    return v->first;
#ifdef _IF_NULL_
    }
    return NULL;
#endif
}

CPUBLIC void* ms_vector_back(ms_vector v) {
#ifdef _IF_NULL_
    if (!ms_vector_empty(v)) {
#endif
    return v->first+v->size*(v->count-1);
#ifdef _IF_NULL_
    }
    return NULL;
#endif
}

CPUBLIC void* ms_vector_insert(ms_vector v, size_t index, void* data) {
#ifdef _IF_NULL_
    if (v) {
#endif
    if (index >= v->count) {
        index = v->count;
        return ms_vector_push_back(v, data);
    }
    if (v->count == v->max_count) {
        ms_vector_grow(v);
    }
    if (v->count < v->max_count) {
        unsigned char* thisp = v->first+v->size*index;
        memmove(thisp+v->size, thisp, (v->count-index)*v->size);
        //赋值
        v->fs.construct(thisp);
        v->fs.copy(thisp, data);
        ++v->count;
        return thisp;
    }
#ifdef _IF_NULL_
    }
#endif
    return NULL;
}

CPUBLIC void ms_vector_remove(ms_vector v, size_t index) {
#ifdef _IF_NULL_
    if (ms_vector_size(v)) {
#endif
    if (index < v->count) {
        if (index == v->count-1) {
            ms_vector_pop_back(v);
        }
        unsigned char* p = v->first+index*v->size;
        v->fs.destroy(p);
        memmove(p, p+v->size,(v->count-index-1)*v->size);
        --v->count;
        if (v->count < v->max_count / 2 && v->count > v->step) {
            size_t new_count = (v->count+v->step)/v->step*v->step;
            ms_vector_reallocate(v, new_count);
        }
    }
#ifdef _IF_NULL_
    }
#endif
}

CPUBLIC void* ms_vector_at(ms_vector v,size_t pos) {
#ifdef _IF_NULL_
    if (v) {
#endif
    if (pos < v->count) {
        return v->first + pos*v->size;
    }
#ifdef _IF_NULL_
    }
#endif
    return NULL;
}

CPUBLIC void* ms_vector_data(ms_vector v) {
#ifdef _IF_NULL_
    if (v) {
#endif
    return v->first;
#ifdef _IF_NULL_
    }
    return NULL;
#endif
}

static inline void ms_vector_buildheap(ms_vector v, size_t pos, size_t size, bool (*data_cmp)(void *left, void* right), void (*data_swap)(void *left, void* right)) {
    size_t p = pos; //父节点
    size_t i = 2 * p + 1; //左子节点
    while (i < size) {
        // 让key先指向子节点中最大(小)的节点
        if (i + 1 < size && data_cmp(v->first+i*v->size,  v->first+(i+1)*v->size)) {
            ++i;
        }
        if (!data_cmp(v->first+p*v->size, v->first+i*v->size)) {
            break;//父节点都不比子节点小(大)，不用交换，那么就直接终止循环了
        }
        data_swap(v->first+p*v->size, v->first+i*v->size);// 如果发现子节点更大(小)，则进行值的交换
        // 如果子节点更换了，那么，以子节点为根的子树会受到影响
        // 所以，循环对子节点所在的树继续进行判断
        p = i;	//命i为父节点
        i = 2 * p + 1; //左子节点
    }
}

CPUBLIC void ms_vector_sort(ms_vector v, bool (*data_cmp)(void *left, void* right), void (*data_swap)(void *left, void* right)) {
    if (NULL == v || v->count < 2) return;
    if (v->count == v->max_count)
        ms_vector_grow(v);
    if (v->count == v->max_count) return;
    //建立堆
    size_t i = v->count / 2; //从最后的子树开始调整
    for (;i > 0;--i) {
        ms_vector_buildheap(v, i-1, v->count, data_cmp, data_swap);
    }
    //排序
    for (i=v->count-1;i>0;--i) {
        data_swap(v->first, v->first+i*v->size);
        ms_vector_buildheap(v, 0, i, data_cmp, data_swap);
    }
}


CPUBLIC void ms_vector_sort_default(ms_vector v) {
    ms_vector_sort(v, ms_type_less, ms_type_swap);
}

#endif // MSC_VECTOR_H
